#include <iostream>
#include <list>
#include <cstring>
#define INF 999999
#define NIL -1
using namespace std;
struct Edge
{
    int start;
    int end;
    int length;
    Edge(){}
    Edge(int s,int e,int l){start=s;end=e;length=l;}
    bool operator<(const Edge& e)
    {
        return this->length<e.length;
    }
    friend ostream& operator<<(ostream& out,const Edge& obj)
    {
        out<<obj.start<<"-"<<obj.end<<":"<<obj.length;
        return out;
    }
};

//图类,使用邻接矩阵实现
class Graph
{
    private:
        int V;//图包含点数
        list<Edge> ** adjList; //存储每个节点的邻接边
        //初始化变量
        void init(int s);

        //松弛操作
        void relax(int u,int v,int w);
	public:

        //根据点数构造图
		Graph(int V);

        //析构函数
        ~Graph();
        //根据起点和终点构造一条边
        void addEdge(int start,int end,int weight=1);

        //打印图信息
        void printMap();
    
        //Dijkstra算法，源点为s
        void dijkstra(int s);

        //Bellman-Ford算法
        bool bellmanFord(int s);
};
